package com.cat.dataStructure02;

import com.cat.binaryTree.Pair;

import java.util.Arrays;
import java.util.PriorityQueue;

/**
 *   @description https://leetcode.cn/problems/meeting-rooms-iii/
 *   @author 曲大人的喵
 *   @create 2025/10/28 18:49
 *   @since JDK17
 */

public class Solution74 {
    public int mostBooked(int n, int[][] meetings) {
        PriorityQueue<Integer> h1 = new PriorityQueue<>();
        PriorityQueue<Pair<Long, Integer>> h2 = new PriorityQueue<>((a, b) -> {
            long k1 = a.getKey(), k2 = b.getKey();
            if (k1 != k2) {
                return Long.compare(k1, k2);
            } else {
                return a.getValue() - b.getValue();
            }
        });

        int[] cnt = new int[n];
        int ans = 0, m = meetings.length;
        for (int i = 0; i < n; i++) {
            h1.add(i);
        }
        Arrays.sort(meetings, (a, b) -> a[0] - b[0]); // 根据开始时间排序
        for (int i = 0; i < m; i++) {
            long st = meetings[i][0], end = meetings[i][1];
            while (!h2.isEmpty() && st >= h2.peek().getKey()) { // 该会议已经结束
                h1.add(h2.poll().getValue());
            }
            int x;
            if (h1.isEmpty()) {
                var p = h2.poll();
                end += p.getKey() - st;
                x = p.getValue();
            } else {
                x = h1.poll();
            }
            ++cnt[x];
            h2.add(new Pair(end, x));
        }
        // 求最大值
        for (int i = 0; i < n; i++) {
            if (cnt[i] > cnt[ans]) {
                ans = i;
            }
        }

        return ans;
    }
}
